package backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 78.子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 */
public class subsets {
    /**
     * 一刷，当时不知道为啥会写这样的代码，强行套之前模板收集结果的逻辑，要么估计是chatgpt生成的要么当时对回溯理解不够清楚，自己没印象了，直接看二刷的
     */
    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i <= nums.length; i++) {
            List<Integer> list =new ArrayList<>();
            backtrack(nums,i,0,res,list);
        }
        return res;
    }
    public void backtrack(int[] nums,int k,int start,List<List<Integer>> res,List<Integer> list) {
        if(list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            backtrack(nums,k,i+1,res,list);
            list.remove(list.size()-1);
        }
    }

    /**
     * 二刷
     * 逻辑更清楚更简洁
     * hot100一刷
     * hot100二刷
     */
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> subsets(int[] nums) {
            backtracking(nums, 0);
            return res;
        }

        public void backtracking(int[] nums, int start) {

            res.add(new ArrayList<>(path));

            for (int i = start; i < nums.length; i++) {
                path.add(nums[i]);
                backtracking(nums, i + 1);
                path.removeLast();
            }
        }
    }
}
